package test;

import com.sun.org.apache.bcel.internal.generic.SWAP;

import java.util.Arrays;

/**
 * 描述：
 *
 * @author hl
 * @version 1.0
 * @date 2020/10/30 21:19
 */
public class HeapSort {
    public static void main(String[] args) throws InterruptedException {
        int[] arr = {2, 6, 8, 4, 4, 1, 3, 9, 6, 8};
        new HeapSort().heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public void heapSort(int[] arr){
        if (arr == null || arr.length < 2) {
            return ;
        }
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while(heapSize > 0){
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }
    public void heapInsert(int[] arr, int index){
        int parent = (index - 1) >> 1;
        while(parent >= 0 && arr[parent] < arr[index]){
            swap(arr, index, parent);
            index = parent;
            parent = (index - 1) >> 1;
        }
    }

    public void heapify(int[] arr, int index, int heapSize){
        int left = (index << 1) + 1;
        int lagest = 0;
        while(left < heapSize){
            lagest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;
            lagest = arr[lagest] > arr[index] ? lagest : index;
            if (lagest == index) {
                return ;
            }
            swap(arr, lagest, index);
            index = lagest;
            left = (index << 1) + 1;
        }
    }


    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
